
#include <iostream>
#include <vector>
using namespace std;

template<class T>
class MySort
{
public:
    // 类模板的静态方法声明
    // O(n^2)
    static void selectSort(T arr[], int len);
    static void bubbleSort(T arr[], int len);
    static void insertSort(T arr[], int len);

    // O(nlogn)
    static void mergeSort(T arr[], int len);
};

template<typename T>
void mySwap(T& v1, T& v2) {
    T temp = v1;
    v1 = v2;
    v2 = temp;
}

// 类模板的 静态模板方法 实现
template<typename T>
void MySort<T>::selectSort(T arr[], int len) {
    // 作n-1次后 最后剩下的为最大值
    for(int i = 0; i < len - 1; i++) {
        int minIdx = i;
        for(int j = i + 1; j < len; j++) {
            if(arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if(i != minIdx) mySwap(arr[i], arr[minIdx]);
    }
}

template<typename T>
void MySort<T>::bubbleSort(T arr[], int len) {
    for(int i = 0; i < len - 1; i++) {
        // 作个小优化 当发现待排序序列有序时，整个序列有序跳出循环
        bool ordinal = true;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                mySwap(arr[j], arr[j + 1]);
                ordinal = false;
            }
        }
        if(ordinal) break;
    }
}

template<typename T>
void MySort<T>::insertSort(T arr[], int len) {
    // 这种写法有点像冒泡
    // 0~0只有一个数，认为有序
    // for(int i = 1; i < len; i++) { // 让0~i上有序
    //     for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
    //         mySwap(arr[j], arr[j + 1]);
    //     }
    // }

    // 使用 while循环来进行插入排序
    for(int i = 1; i < len; i++) {
        int toBeInsert = arr[i], j = i;
        while(j > 0 && toBeInsert < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        // 找到比其小的数
        if(j != i) {
            arr[j] = toBeInsert;
        }
    }
}

template<typename T>
void merge(T arr[], int L, int R, int mid) {
    vector<T> vecHelp;
    int idx1 = L, idx2 = mid + 1;
    // 优先将小的值合并到 辅助数组中
    while(idx1 <= mid && idx2 <= R) {
        vecHelp.push_back(arr[idx1] > arr[idx2] ? arr[idx2++] : arr[idx1++]);
    }
    // 以上执行完成后 一定有一边的数值没有合并完成
    while(idx1 <= mid) {
        vecHelp.push_back(arr[idx1++]);
    }
    while(idx2 <= R) {
        vecHelp.push_back(arr[idx2++]);
    }
    // 最后将辅助数组中的值拷贝回 要排序的数组
    for(int i = 0; i < vecHelp.size(); i++) {
        arr[L + i] = vecHelp[i];
    }
}
template<typename T>
void process(T arr[], int L, int R) {
    if(L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, R, mid);
}
template<typename T>
void MySort<T>::mergeSort(T arr[], int len) {
    process(arr, 0, len - 1);
}